package Demo51;


/**
 *  翻转对
 * https://leetcode.cn/problems/reverse-pairs/
 */
class Solution {
    int[] tmp;
    public int reversePairs(int[] nums) {
        int len = nums.length;
        tmp = new int[len];

        return margetSort(nums, 0, len - 1);
    }

    private int margetSort(int[] nums, int begin, int end) {
        if(begin >= end) {
            return 0;
        }
        int ret = 0;
        int mid = (begin + end) / 2;
        ret += margetSort(nums,begin,mid);
        ret += margetSort(nums,mid + 1, end);
        int  left = begin, right = mid + 1;
        while(left <= mid && right <= end) {
            Long n = nums[right] * 2l;
            if(nums[left] > n) {
                ret += (mid - left + 1);
                right++;
            }else {
                left++;
            }
        }
        int i = 0;
        left = begin;
        right = mid + 1;

        while(left <= mid && right <= end) {
            if(nums[left] <= nums[right]) {
                tmp[i++] = nums[left++];
            }else {
                tmp[i++] = nums[right++];
            }
        }
        while(left <= mid) {
            tmp[i++] = nums[left++];
        }
        while(right <= end) {
            tmp[i++] = nums[right++];
        }

        for(int j = begin; j <= end; j++) {
            nums[j] = tmp[j - begin];
        }
        return ret;
    }
}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int ret = solution.reversePairs(new int[] {2147483647,2147483647,2147483647,2147483647,2147483647,2147483647});
        System.out.println(ret);

    }
}